//
//  PathStep.m
//  9A
//
//  Created by Jacky.Chen on 13-7-1.
//
//

#import "PathStep.h"
#import "cocos2d.h"

@interface PathStep()
- (BOOL)containCell:(CGPoint)pos closedArray:(NSMutableArray*) arrClosed;
- (BOOL)containStep:(PathStep*)p closedArray:(NSMutableArray*) arrClosed;
-(id)findShortestPath:(PathStep*)current targetCell:(PathStep*)target closedArray:(NSMutableArray*) arrClosed openedArray:(NSMutableArray*) arrOpened shortestArray:(NSMutableArray*) arrShortPath;

@end

@implementation PathStep
@synthesize position;
@synthesize gScore;
@synthesize hScore;
@synthesize parent;

@synthesize leftPosition;
@synthesize rightPosition;
@synthesize upPosition;
@synthesize downPosition;

@synthesize cellX;
@synthesize cellY;

@synthesize currentPathIndex;
@synthesize isClosed;

+(id)initWithPositionAndCloseArray:(CGPoint)pos closedArray:(NSMutableArray*) arrClosed
{
    return  [[[self alloc] initWithPosition:pos closedArray:arrClosed ] autorelease];
}
- (id)initWithPosition:(CGPoint)pos closedArray:(NSMutableArray*) arrClosed
{
	if ((self = [super init])) {
		gScore = 0;
		hScore = 0;
		parent = nil;
        self.isClosed = NO;
        //get the current cell index(X,Y) X:0-8  Y:0-8
        cellX = pos.x;
        cellY = pos.y;
        
        //get the cell middle Coordinate
        //this is the openGL coorinate
        float coordinateX = floor(pos.x+1)*ROWS_WIDTH-ROWS_WIDTH/2 + WIDTH_PADING;// x*35 + 35/2;
        float coordinateY = floor(pos.y+1)*ROWS_HEIGHT - ROWS_HEIGHT/2 + HEIGHT_PADING;
        
        position.x = coordinateX;
        position.y = coordinateY;
        //find the left position
        if(cellX==0){
            leftPosition = 0;
        }
        else if([self containCell:ccp(cellX-1,cellY) closedArray:arrClosed])
        {
            leftPosition = 0;
        }
        else{
            leftPosition = -1;
        }
        if(cellX==MAX_ROWS)
        {
            rightPosition = 0;
        }
        else if([self containCell:ccp(cellX+1,cellY) closedArray:arrClosed])
        {
            rightPosition = 0;
        }
        else{
            rightPosition = 1;
        }
        
        if(cellY==0){
            upPosition = 0;
        }
        else if([self containCell:ccp(cellX,cellY-1) closedArray:arrClosed])
        {
            upPosition = 0;
        }
        else{
            upPosition = -1;
        }
        
        if(cellY==MAX_COLS){
            downPosition = 0;
        }
        
        else if([self containCell:ccp(cellX,cellY+1) closedArray:arrClosed])
        {
            downPosition = 0;
        }
        else{
            downPosition = 1;
        }
        
	}
	return self;
}

- (id)initWithParent:(PathStep*)fromParent targetPos:(PathStep*)target nextCellX:(int)x nextCellY:(int)y closedArray:(NSMutableArray*) arrClosed
{
    if ((self = [super init])) {
		gScore = fromParent.gScore + 1;
        hScore = abs(x-target.cellX) + abs(y-target.cellY);
		parent = fromParent;
        self.isClosed = NO;
        //get the current cell index(X,Y) X:0-8  Y:0-8
        cellX = x;
        cellY = y;
        
        //get the cell middle Coordinate
        //this is the openGL coorinate
        float coordinateX = floor(x+1)*ROWS_WIDTH-ROWS_WIDTH/2 + WIDTH_PADING;// x*35 + 35/2;
        float coordinateY = floor(y+1)*ROWS_HEIGHT - ROWS_HEIGHT/2 + HEIGHT_PADING;
        position.x = coordinateX;
        position.y = coordinateY;
        
        //find the left position
        if(cellX==0){
            leftPosition = 0;
        }
        //if the close array contain
        //for example:
        //     -1
        //    -1p+1
        //     +1
        else if(cellX-1==fromParent.cellX)
        {
            leftPosition = 0;
        }
        else if([self containCell:ccp(cellX-1,cellY) closedArray:arrClosed])
        {
            leftPosition = 0;
        }
        else{
            leftPosition = -1;
        }
        if(cellX==MAX_ROWS)
        {
            rightPosition = 0;
        }
        else if(cellX+1==fromParent.cellX)
        {
            rightPosition = 0;
        }
        else if([self containCell:ccp(cellX+1,cellY) closedArray:arrClosed])
        {
            rightPosition = 0;
        }
        else{
            rightPosition = 1;
        }
        
        if(cellY==0){
            upPosition = 0;
        }
        //if the close array contain
        else if(cellY-1==fromParent.cellY)
        {
            upPosition = 0;
        }
        else if([self containCell:ccp(cellX,cellY-1) closedArray:arrClosed])
        {
            upPosition = 0;
        }
        else{
            upPosition = -1;
        }
        
        if(cellY==MAX_COLS){
            downPosition = 0;
        }
        //if the close array contain
        else if(cellY+1==fromParent.cellY)
        {
            downPosition = 0;
        }
        else if([self containCell:ccp(cellX,cellY+1) closedArray:arrClosed])
        {
            downPosition = 0;
        }
        else{
            downPosition = 1;
        }
	}
	return self;
}
//checked the current point had occupied
- (BOOL)containStep:(PathStep*)p closedArray:(NSMutableArray*) arrClosed
{
    return [self containCell:ccp(p.cellX,p.cellY) closedArray:arrClosed];
}
- (BOOL)containCell:(CGPoint)pos closedArray:(NSMutableArray*) arrClosed
{
    bool isContain = NO;
    for (NSValue *value in arrClosed) {
        CGPoint  a = [value CGPointValue];
        //CCLOG(@"containCell [%.0f,%.0f],[%.0f,%.0f]",a.x,a.y,pos.x,pos.y);
        if(a.x==pos.x && a.y==pos.y )
        {
            isContain = YES;
            //CCLOG(@"containCell *****[%.0f,%.0f],[%.0f,%.0f]********",a.x,a.y,pos.x,pos.y);
        }
    }
    return isContain;
}
- (void)print
{
    CCLOG(@"PathStep data with:%@", [self description]);
}
- (BOOL)closed
{
    return !(self.leftPosition == self.rightPosition ==self.upPosition ==self.downPosition);
}


//A* shortest path
//gScore:the current position from the start position moved steps
//hScore:the current position to the target position distance
//fScore: gScore + hScore the lest is the best path
//so lest began to find the path,and find the lest fScore and move,and every step we check the fScore
-(id)findShortestPath:(PathStep*)current targetCell:(PathStep*)target closedArray:(NSMutableArray*) arrClosed;
{
    NSMutableArray* arrShortPath = [[[NSMutableArray alloc] init] autorelease];
    return [self findShortestPath:current targetCell:target closedArray:arrClosed shortestArray:arrShortPath];
}
-(id)findShortestPath:(PathStep*)current targetCell:(PathStep*)target closedArray:(NSMutableArray*) arrClosed shortestArray:(NSMutableArray*) arrShortPath
{
    //the first load
    if(arrShortPath.count==0 && !(current.leftPosition==0 && current.rightPosition==0 && current.upPosition==0 && current.downPosition==0))
    {
        //we find the shortest path then rescurie lookup
        if(current.leftPosition!=0 )
        {
            PathStep* pLeft = [[[PathStep alloc] initWithParent:current  targetPos:target  nextCellX:(current.cellX + current.leftPosition) nextCellY:current.cellY closedArray:[arrClosed mutableCopy]] autorelease];
            NSMutableArray* arr = [[NSMutableArray alloc] initWithObjects:pLeft, nil];
            [arrShortPath addObject:arr];
            //the count is not the right index, so we need to -1
            pLeft.currentPathIndex  = arrShortPath.count-1;
            NSValue *closedPoint = [NSValue valueWithCGPoint:ccp(pLeft.cellX,pLeft.cellY)];
            [arrClosed addObject:closedPoint];
        }
        if(current.rightPosition!=0)
        {
            PathStep* p =  [[[PathStep alloc] initWithParent:current  targetPos:target  nextCellX:(current.cellX + current.rightPosition) nextCellY:current.cellY closedArray:[arrClosed mutableCopy]] autorelease];
            NSMutableArray* arr = [[NSMutableArray alloc] initWithObjects:p, nil];
            [arrShortPath addObject:arr];
            //the count is not the right index, so we need to -1
            p.currentPathIndex = arrShortPath.count-1;
            NSValue *closedPoint = [NSValue valueWithCGPoint:ccp(p.cellX,p.cellY)];
            [arrClosed addObject:closedPoint];
        }
        if(current.upPosition!=0)
        {
            PathStep* p = [[[PathStep alloc] initWithParent:current  targetPos:target  nextCellX:current.cellX nextCellY:(current.cellY +current.upPosition) closedArray:[arrClosed mutableCopy]] autorelease];
            NSMutableArray* arr = [[NSMutableArray alloc] initWithObjects:p, nil];
            [arrShortPath addObject:arr];
            //the count is not the right index, so we need to -1
            p.currentPathIndex = arrShortPath.count-1;
            NSValue *closedPoint = [NSValue valueWithCGPoint:ccp(p.cellX,p.cellY)];
            [arrClosed addObject:closedPoint];
        }
        if(current.downPosition!=0)
        {
            PathStep* p = [[[PathStep alloc] initWithParent:current  targetPos:target  nextCellX:current.cellX nextCellY:(current.cellY +current.downPosition) closedArray:[arrClosed mutableCopy]] autorelease];
            NSMutableArray* arr = [[NSMutableArray alloc] initWithObjects:p, nil];
            [arrShortPath addObject:arr];
            //the count is not the right index, so we need to -1
            p.currentPathIndex = arrShortPath.count-1;
            NSValue *closedPoint = [NSValue valueWithCGPoint:ccp(p.cellX,p.cellY)];
            [arrClosed addObject:closedPoint];
            
            
        }
        //find the min fScore
        int iCount = arrShortPath.count;
        PathStep* pMin;
        for (int i=0; i<iCount; ++i) {
            NSMutableArray* arr=(NSMutableArray*)[arrShortPath objectAtIndex:i];
            PathStep* p = [arr lastObject];
            
            pMin = p;
            for (int j=i+1; j<iCount; ++j) {
                NSMutableArray* arr_j=(NSMutableArray*)[arrShortPath objectAtIndex:j];
                PathStep* pj = [arr_j lastObject];
                if (pj.fScore<p.fScore) {
                    p = pj;
                    pMin = p;
                }
            }
            break;
        }
        return  [self findShortestPath:pMin targetCell:target closedArray:arrClosed  shortestArray:arrShortPath];
    }
    else if(arrShortPath.count==0 && (current.leftPosition==0 && current.rightPosition==0 && current.upPosition==0 && current.downPosition==0))
    {
        [arrShortPath removeAllObjects ];
        return nil;
    }
    //if the current is the end of target
    else if([current isEqual:target])
    {
        //return the shortest path
        NSMutableArray* arr =[[arrShortPath objectAtIndex:current.currentPathIndex] mutableCopy];
        
        [arrShortPath removeAllObjects];
        [arrClosed removeAllObjects];
        //arrShortPath = arr;
        PathStep* p = [arr lastObject];
        p.isClosed = YES;
        return arr ;
    }
    //if the current position had end the road, then return nil
    else if(![current isEqual:target] && current.leftPosition==0 && current.rightPosition==0 && current.upPosition==0 && current.downPosition==0)
    {
        current.isClosed = YES;
        bool isAllClosed = YES;
        PathStep* p;
        for (int i=0; i<arrShortPath.count; ++i) {
            NSMutableArray* arr =[arrShortPath objectAtIndex:i];
            p = [arr lastObject];
            if (![p isEqual:current]) {
                if (!p.isClosed) {
                    isAllClosed = NO;
                    break;
                }
            }
            
        }
        if(!isAllClosed)
        {
            return [self findShortestPath:p targetCell:target closedArray:arrClosed  shortestArray:arrShortPath];
            
        }
        else{
            [arrShortPath removeAllObjects];
            [arrClosed removeAllObjects];
            return nil;
        }
        
    }
    //we need to rescure all the path
    else{
        // find the shortest path then go on
        bool isClosedFlag = YES;
        while (isClosedFlag) {
            
            BOOL isDone = YES;
            //try the shortest path
            int iCount = arrShortPath.count;
            for (int i=0; i<iCount; ++i) {
                NSMutableArray* arr=(NSMutableArray*)[arrShortPath objectAtIndex:i];
                PathStep* p = [arr lastObject];
                if (! p.isClosed) {
                    isDone = NO;
                    break;
                }
            }
            //there no path to try
            if (isDone) {
                [arrShortPath removeAllObjects];
                return nil;
            }
            
            int iMax = -1;
            PathStep* pMin;
            for (int i=0; i<iCount; ++i) {
                NSMutableArray* arr=(NSMutableArray*)[arrShortPath objectAtIndex:i];
                PathStep* p = [arr lastObject];
                if(!p.isClosed)
                {
                    pMin = p;
                    iMax = i;
                    for (int j=i+1; j<iCount; ++j)
                    {
                        NSMutableArray* arr_j=(NSMutableArray*)[arrShortPath objectAtIndex:j];
                        PathStep* pj = [arr_j lastObject];
                        if(pj.isClosed==NO && ( pj.fScore<p.fScore || (pj.fScore==p.fScore && pj.hScore<p.hScore) ))
                        {
                            iMax = j;
                            p = pj;
                            pMin = p;
                        }
                    }
                    break;
                }
                
            }
            //all the path closed
            if (iMax==-1) {
                return nil;
            }
            CCLOG(@"The min is [%d,%d]",pMin.cellX,pMin.cellY);
            //we got the shortest point
            //we  need to know the shortest left right up down position then go on
            NSMutableArray* arr4d = [[[NSMutableArray alloc] init] autorelease];
            if(pMin.leftPosition!=0)
            {
                PathStep* pLeft = [[[PathStep alloc] initWithParent:pMin  targetPos:target  nextCellX:(pMin.cellX + pMin.leftPosition) nextCellY:pMin.cellY closedArray:[[arrClosed mutableCopy] autorelease]] autorelease];
                if(![pLeft containStep:pLeft closedArray:arrClosed])
                    [arr4d addObject:pLeft];
            }
            if(pMin.rightPosition!=0)
            {
                PathStep* p =  [[[PathStep alloc] initWithParent:pMin  targetPos:target  nextCellX:(pMin.cellX + pMin.rightPosition) nextCellY:pMin.cellY closedArray:[[arrClosed mutableCopy] autorelease]] autorelease];
                if(![p containStep:p closedArray:arrClosed])
                    [arr4d addObject:p];
            }
            if(pMin.upPosition!=0)
            {
                PathStep* p = [[[PathStep alloc] initWithParent:pMin  targetPos:target  nextCellX:pMin.cellX nextCellY:(pMin.cellY +pMin.upPosition) closedArray:[[arrClosed mutableCopy] autorelease]] autorelease];
                if(![p containStep:p closedArray:arrClosed])
                    [arr4d addObject:p];
                
            }
            if(pMin.downPosition!=0)
            {
                PathStep* p = [[[PathStep alloc] initWithParent:pMin  targetPos:target  nextCellX:pMin.cellX nextCellY:(pMin.cellY +pMin.downPosition) closedArray:[[arrClosed mutableCopy] autorelease]] autorelease];
                if(![p containStep:p closedArray:arrClosed])
                    [arr4d addObject:p];
                
            }
            if (arr4d.count==0) {
                pMin.isClosed = YES;
            }
            else if (arr4d.count>0) {
                //only one step is the next step
                PathStep* pMinNext;
                int iMinNext = 0;
                for (int i=0; i<arr4d.count; ++i) {
                    
                    PathStep* p = [arr4d objectAtIndex:i];
                    pMinNext = p;
                    for (int j=i+1; j<arr4d.count; ++j) {
                        PathStep* pj = [arr4d objectAtIndex:j];
                        if (pj.fScore<p.fScore) {
                            p = pj;
                            pMinNext = p;
                            iMinNext = j;
                        }
                    }
                    break;
                }
                
                //add the path to find path list(arrShortPath)
                NSMutableArray* arrMin = [[(NSMutableArray*)[arrShortPath objectAtIndex:pMin.currentPathIndex] mutableCopy] autorelease];
                for (int i=0; i<arr4d.count; ++i) {
                    if (i==iMinNext) {
                        NSMutableArray* arrMinCurrent = (NSMutableArray*)[arrShortPath objectAtIndex:pMin.currentPathIndex];
                        PathStep* p = [arr4d objectAtIndex:i];
                        p.currentPathIndex = pMin.currentPathIndex;
                        [arrMinCurrent addObject:p];
                        
                        NSValue *closedPoint = [NSValue valueWithCGPoint:ccp(p.cellX,p.cellY)];
                        CCLOG(@"closedPoint [%d,%d]",p.cellX ,p.cellY);
                        [arrClosed addObject:closedPoint];
                        
                    }
                    else
                    {
                        PathStep* p = [arr4d objectAtIndex:i];
                        NSMutableArray* arrMinNew = [(NSMutableArray*)[arrMin mutableCopy] autorelease];
                        [arrMinNew addObject:p];
                        [arrShortPath addObject:arrMinNew];
                        p.currentPathIndex = arrShortPath.count-1;
                        
                        NSValue *closedPoint = [NSValue valueWithCGPoint:ccp(p.cellX,p.cellY)];
                        CCLOG(@"closedPoint [%d,%d]",p.cellX ,p.cellY);
                        [arrClosed addObject:closedPoint];
                    }
                }
               
                NSValue *closedPoint = [NSValue valueWithCGPoint:ccp(pMinNext.cellX,pMinNext.cellY)];
                CCLOG(@"closedPoint [%d,%d]",pMinNext.cellX ,pMinNext.cellY);
                [arrClosed addObject:closedPoint];
                if(![pMinNext isEqual:target]  && (pMinNext.upPosition==0 && pMinNext.downPosition==0 && pMinNext.leftPosition==0 && pMinNext.rightPosition==0))
                {
                    pMinNext.isClosed = YES;
                }
                else{
                    return [self findShortestPath:pMinNext targetCell:target closedArray:arrClosed   shortestArray:arrShortPath];
                }
            }
        }
    }
}

- (NSString *)description
{
	return [NSString stringWithFormat:@"%@  pos=[%.0f;%.0f] cell[%d,%d]  g=%d  h=%d  f=%d leftPosition=%d rightPosition=%d upPosition=%d downPosition=%d",
            [super description], self.position.x, self.position.y, self.cellX,self.cellY, self.gScore, self.hScore, [self fScore],
            self.leftPosition, self.rightPosition, self.upPosition,self.downPosition];
}
- (BOOL)isEqual:(PathStep *)other
{
	return self.cellX == other.cellX && self.cellY == other.cellY;
}
- (int)fScore
{
	return self.gScore + self.hScore; 
}
@end

